1. Field of the Invention
The present invention relates to allocation of bandwidth within in a chain of devices interconnected via a plurality of point-to-point communication links.
2. Background Art
This section is intended to introduce the reader to various aspects of art which may be related to various aspects of the present invention which are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present invention. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art.
Many computer systems generally have been designed around a shared bus architecture, in which one or more host processors and a host memory are coupled to a shared host bus. Transactions between processors and accesses to memory all occur on the shared bus. Such computer systems typically include an input/output (I/O) subsystem which is coupled to the shared host bus via an I/O bridge which manages information transfer between the I/O subsystem and the devices coupled to the shared host bus. Many I/O subsystems also generally follow a shared bus architecture, in which a plurality of I/O or peripheral devices are coupled to a shared I/O bus. The I/O subsystem may include several branches of shared I/O buses interconnected via additional I/O bridges. These shared I/O busses typically use a central arbiter to grant use of the bus to the devices connected to it. Fair allocation of the available bandwidth on the bus may be guaranteed by implementing a fair arbitration algorithm in the central arbiter.
U.S. Patent Publication No. US 2002/0083233 to Owen et al., the disclosure of which is incorporated in its entirety herein by reference, discloses a method for fairly allocating bandwidth to devices connected by a plurality of point-to-point links, in which arbitration is distributed among the devices rather than performed by a central arbiter. As illustrated in FIG. 1, which summarizes FIG. 2 of Owen et al., each device 10a, 10b, and 10c is configured for selecting between transmitting its own packet (i.e., a local packet), and a received packet from a supplying device, according to a corresponding determined insertion rate. The I/O devices (10) and bridge (12) each contain buffers (Rx) associated with each incoming link, into which packets are placed as they are received. As packets are removed from the buffers (due to being consumed internally or forwarded to the next device in the chain), buffer release messages are sent back to the transmitter at the other end of the link, indicating that buffers have been freed. A transmitter may only send packets when the corresponding receiver has indicated that it has space to receive them. No packets are dropped. Therefore, the limiting factor that determines the maximum rate at which packets may be transmitted along a link may be either the raw bandwidth of the link, or the rate at which buffer releases are received, whichever is lower.
In the case where all 3 links (16a, 16b, 16c) have the same available bandwidth, and all 3 I/O devices (10a, 10b, 10c) are attempting to send streams of packets to the bridge at a total rate exceeding the available bandwidth of link 16a, links 16b and 16c may back up. Device 10a's receive buffers may be filling with packets originating from device 10b and device 10c at up to the full link bandwidth of link 16b, but the buffers will be draining at a lower rate, since insertion of a packet originating at device 10a does not drain a receive buffer. Since the buffers are filling faster than they are draining, they will eventually fill to capacity, causing device 10b to stop sending packets across link 16b. At that point, device 10b will only be able to send a packet when it receives a buffer release from 10a, which will only happen when device 10a frees a buffer by forwarding a packet. Thus, the maximum usable bandwidth on link 16b has been reduced to the amount of bandwidth actually used on link 16a by packets forwarded from 16b. This pattern repeats with each succeeding link.
Owen et al. describes that each I/O device 10a, 10b, and 10c is configured for determining an insertion rate (INS_R) for transmitting a corresponding local packet relative to transmission of received packets from the corresponding connected supplying device. As described below, each I/O device that receives packets from a supplying devices determines an “issue rate” (ISR) for each supplying device (defined as the number of packets received from a corresponding supplying device relative to the total number of received packets), and sets its insertion rate (INS_R) to equal the highest determined issue rate.
Referring to traffic from the I/O device 10c destined to the bridge 12 via the I/O device 10b, the I/O device 10a, and the bridge 12, the I/O device 10c is deemed the supplying device relative to the I/O device 10b, and the I/O device 10b is deemed the supplying device relative to the I/O device 10a. 
According to Owen et al., each device independently makes the decision when to forward a packet from its receive buffers or insert a locally generated packet. In the case where there are only packets to be forwarded or packets to be inserted, but not both, and a buffer is available to receive a packet, the next packet of the appropriate type can go; when there is no contention for the output link, either type of traffic is allowed to use all the available bandwidth that it can. In the case of bandwidth contention, where packets from both sources are available to be sent, bandwidth is allocated based on each device matching its insertion rate (INS_R) to the highest issue rate (ISR) detected from among the supplying devices. For example, the I/O device 10b determines that the I/O device 10c has a 100% issue rate (ISRC=1), where all packets received by device 10b are from device 10c due to the I/O device 10c being at the end of the chain 14; hence the I/O device 10b is configured for selecting a 100% insertion rate (INS_R=1), namely inserting for transmission one of its own packets (i.e., its local packet) (P_B) for each received packet (P_C) from its corresponding supplying I/O device 10c, ensuring an equal distribution of a local packet (P_B) and a received packet (P_C) on the transmission link 16b. Hence, for every received packet (P_C) that is forwarded by the I/O device 10b (also referred as a “forwarded packet”), the I/O device 10b is able to insert a local packet (P_B).
The I/O device 10a, however, cannot insert its corresponding local packet (P_A) for every received packet from its corresponding supplying I/O device 10b via the connected transmission link 16b, since an equal selection would result in the traffic to the bridge 12 on transmission link 16a having a distribution of 50% local packets (P_A) from the I/O device 10a, 25% packets (P_B) from device 10b, and 25% packets from device 10c. Hence, the I/O device 10 is configured for determining the source of each of the received packets on the corresponding connected transmission link 16b to determine the highest issue rate (ISR) for any one of the supplying I/O devices over a prescribed sampling interval. As illustrated in FIG. 1, the I/O device 10a is able to determine the issue rates of devices 10b and 10c such that, averaged over some sampling period, for every two received packets via transmission link 16b, one packet is from device 10b and one packet is from device 10c (ISRB=ISRC=½). Hence, the I/O device 10a sets its insertion rate to equal the highest determined issue rate (INS_R=ISRC=½), such that for every two packets received by the device 10a, the device 10a is configured to insert a local packet (P_A), resulting in one local packet (P_A) for every two received packets from the corresponding connected supplying device 10b. Consequently, equal distribution of packets from the devices 10a, 10b, and 10c can be provided on the transmission link 16a. The foregoing example assumes all links are fully utilized and that each device 10a, 10b, and 10c is assigned an equal priority.
For another example, assume that the device 10c was not utilizing the transmission link 16c at 100% capacity; that is, it did not have a packet to send every time device 10b freed a receive buffer. In that case, since device 10b was draining its receive buffers faster than device 10c was refilling them, device 10b's receive buffers would eventually become empty. Once in that state, they would become nonempty each time a packet was received from device 10c, and then go empty again when that packet was transmitted, until the next packet was received. If device 10b always had locally generated packets to send, then there would be periods when there were both packets to issue and forward, alternating with periods when there were only packets to issue. The issue path would always be granted when there was nothing to forward, allowing device 10b to utilize the extra bandwidth which device 10c did not use. If device 10c was only issuing packets at 33% of the available (as limited by buffer releases from device 10a) bandwidth of link 16b, then device 10c would have its packets forwarded at its rate of issue (33% of the bandwidth of link 16b) and device 10b would have the rest (67%) of the bandwidth of link 16b). In other words, device 10b would be allowed to insert 2 packets for every one of device 10c's packets that it forwarded. Hence, the I/O device 10a would detect, over a pattern of three received packets, that two received packets were from device 10b (ISRB=⅔), and that one received packet was from device 10c (ISRC=⅓), causing the device 10a to set its insertion rate (INS_R) equal to the highest determined issue rate (INS_R=ISRB=⅔), such that the device 10a inserts two local packets (P_A) for every three forwarded packets (P_B or P_C). Consequently, the I/O device outputs onto transmission line 16a repeating pattern of five packets, where two packets are local packets (2*P_A) and three packets are forwarded packets (e.g., 2*P_B and one P_C).